package main

import "fmt"

var count int

func main() {

	DNF(4,0,0,0,0)

	fmt.Println(count)

}

func DNF(n, row, cols, pie, na int) {
	if row >= n {
		count++
		return
	}

	shadow:=1 << n - 1

	bits := (^(cols | pie | na)) & shadow // 获取当前所有空位

	for bits > 0 {
		p := bits & -bits //取最低位的1
		DNF(n, row+1, cols|p, ((pie|p)<<1)&shadow, ((na|p)>>1)&shadow)
		bits = bits & (bits - 1)
	}

}
